"""

https://leetcode-cn.com/problems/reorganize-string/

767. 重构字符串
"""


class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        # d为字典，存储各个字符及其出现次数
        # max_key，max_value 存储出现次数最多的字符 以及 它的出现的次数
        d, max_key, max_value = {}, 'a', 0
        for i in range(len(S)):
            if S[i] not in d:
                d[S[i]] = 1
            else:
                d[S[i]] += 1
            if d[S[i]] > max_value:
                max_key, max_value = S[i], d[S[i]]
        # 根据提示—— 交替放置 “出现次数最多” 的字符。关于“出现次数最多”，我的理解如下所示
        # 例如 'c':2,'a':3,'b':5,'d':7
        # 交替放置则为: cabd cabd abd bd bd
        # 出现次数最多的字符为'd'，交替放置已经摆好了5个，'d'还剩下2个，所以还可以怎么插入呢？
        # 为了更好说明，上边的摆放顺序故意以空格隔开，然后分隔成五组。
        # 可插入位置：
        # 第一组：'d'cabd; c'd'abd; ca'd'bd 3个
        # 第二组：c'd'abd; ca'd'bd 2个
        # 第三组：a'd'bd 1个
        # 。。。后边的组无论怎么插入，'d'始终会相邻
        # 所以，交替放置的'd'个数+可插入位置的个数=5+6=11，这个11也就是'd'为满足题意所要求的最多次数
        # 5+6=11，11这个数为 不包括出现次数最多的字符，即剩余字符出现的次数+1
        # 可以试试其它情况，都是这样。
        # 归纳总结如下：如需满足题意，出现次数最多的字符个数 一定要 小于等于 (不包括出现次数最多的字符，即剩余字符出现的次数+1)，如果不满足，则返回空字符串
        if max_value > 1 + (sum(d.values()) - max_value):
            return ''
        elif len(d) == 1:
            return S
        key_value, res = [list(item) for item in sorted(list(d.items()), key=lambda x: x[1])], ''
        # sub_key，sub_value存储出现次数第二多的字符 以及 它的出现次数
        sub_key, sub_value = key_value[len(key_value)-2][0], key_value[len(key_value)-2][1]
        # 实现交替放置
        for i in range(len(key_value)):
            while key_value[i][1]:
                for j in range(i, len(key_value)):
                    res += key_value[j][0]
                    key_value[j][1] -= 1
            if key_value[i][0] == sub_key:
                break
        # left_value: 出现次数最多的字符进行交替摆放后，还剩下多少个
        left_value, index = max_value - sub_value, 0
        # 实现 剩余字符的插入
        while left_value:
            if index == 0 or (res[index] != max_key and res[index-1] != max_key):
                res = res[:index] + max_key + res[index:]
                left_value -= 1
            index += 1
        return res

if __name__ == '__main__':
    s = Solution()
    a = s.reorganizeString("sasssss")
    print(a)